package com.practice.tree;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class Tree2XML {
	private Node root;
	
	public static void main(String[] args) {
		new Tree2XML().test();
	}
	
	private void test() {
		Node a = new Node("a", null);
		Node b = new Node("b", a);
		Node c = new Node("c", a);
		Node e = new Node("e", b);
		Node h = new Node("h", c);
		Node g = new Node("g", e, h);
		Node d = new Node("d", b, g);
		
		System.out.println(asXML(d));
	}
	
	public String asXML(Node start) {
		HashMap<Node, List> map = new HashMap<Node, List>();
		while (start != null) {
			record(start, map);
			start = start.next;
		}
		return asXML(map, root);
	}
	
	private String asXML(HashMap<Node, List> map, Node node) {
		if (map.get(node) == null) return ("<" + node.name + "/>\n"); 
		
		StringBuffer sb = new StringBuffer();
		sb.append("<" + node.name + ">\n");
		for (Node child : (List<Node>) map.get(node)) {
			sb.append(asXML(map, child));
		}
		sb.append("</" + node.name + ">\n");
		return sb.toString();
	}
	
	private void record(Node node, HashMap<Node, List> map) {
		if (node.parent == null) {
			root = node;
			return;
		}
		
		if (!map.containsKey(node.parent)) {
			map.put(node.parent, new ArrayList<Node>());
		}
		
		if (!map.get(node.parent).contains(node)) {
			map.get(node.parent).add(node);
			record(node.parent, map);
		}
	}
	
	private class Node {
		String 	name;
		Node	parent;
		Node	next;
		
		public Node(String name, Node parent) {
			this.name = name;
			this.parent = parent;
		}
		
		public Node(String name, Node parent, Node next) {
			this.name = name;
			this.parent = parent;
			this.next = next;
		}
	}
}
